package classic150;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2023/12/1 9:38
 * @description <p>leetCode55-跳跃游戏-数组-中等题</p>
 */
public class No55 {
    public static void main(String[] args) {
        int[] nums = {3, 4, 6, 0, 0, 0, 0, 0, 0};
        System.out.println(canJump(nums));
    }

    /**
     * max_1 = num[0] + 0
     * num[max_1]
     * <p>
     * i in [0, max_1]
     * max_2 = num[i] + i
     * <p>
     * i in [max_1, max_2]
     * max_3 = num[i] + i
     * <p>
     * ······
     * <p>
     * i in [max_n-2, max_n-1]
     * max_n = num[i] + i
     * max_n >= nums.length - 1 结束
     *
     * @param nums
     * @return
     */
    public static boolean canJump(int[] nums) {

        int count = 1;
        int max1 = 0;
        int max2 = nums[0];
        int len = max2;
        int temp = nums[max1] + max1;

        while (len < nums.length - 1) {
            if (count == nums.length) {
                return false;
            }

            for (int i = max1; i <= max2; i++) {
                if (nums[i] + i > temp) {
                    len = nums[i] + i;
                    temp = len;
                }
            }

            max1 = max2;
            max2 = len;

            count++;
        }
        return true;
    }
}